package vip.zhenzicheng.algorithm.leetcode.linked_list;

import vip.zhenzicheng.algorithm.ListNode;

/**
 * <a href="https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/">剑指 Offer 22 链表中第k个节点 [简单]</a>
 * 输入一个链表，输出该链表倒数第k个节点，倒数第一个位置从1开始计算。
 * input:[1,2,3,4,5,6],k=3 -> output:[4,5,6]
 *
 * @author zhenzicheng
 * @date: 2022-06-03 11:03
 */
public class LastKNodeOfLinkedList_Offer22 {
  /*
   * 解法1：存放hashMap(index,val)
   * 解法2：存放ArrayList(ListNode)
   * 解法3：求倒数第k个就是正数第(head.length - k + 1)个
   */

  /**
   * 解法4：
   * 快慢指针，求第k个就将快指针先移动k-1个，然后与慢指针一起以相同速度移动，遍历到链表尾节点时，慢指针就是倒数第k个
   */
  public ListNode getKthFromEnd(ListNode head, int k) {
    if (k == 0 || head == null) {
      return null;
    }

    ListNode fast = head, slow = head;
    for (int i = 0; i < k - 1; i++) {
      fast = fast.next;
    }
    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next;
    }

    return slow;
  }
}
